package com.zhupf.part7;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhupf
 * @date 2023年11月09日 9:05
 * @Description
 *
 *  链表的反转
 */
public class ReverseList {


    public static void main(String[] args) {
        ListNode node = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
        ListNode node1 = reverseList(node);
        System.out.println(node1);

    }

    /**
     * @param head
     * @return
     */
    public static ListNode reverseList4(ListNode head) {
        if(head ==null || head.next == null){
            return head;
        }
        ListNode nowNode = reverseList4(head.next);
        head.next.next = head;
        head.next = null;
        return nowNode;
    }


    /**
     * @param head
     * @return
     */
    public static ListNode reverseList5(ListNode head) {
        if(head ==null || head.next == null){
            return head;
        }
        ListNode newNode = new ListNode(0,null);
        ListNode h = head;
        ListNode next;
        while (h != null){
            next = h.next;
            h.next = newNode.next;
            newNode.next = h;
            h = next;
        }
        return newNode.next;
    }



    /**
     * 递归  相当于从末尾迭代，往上收集
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newNode;
    }


    /**
     * 迭代 正向迭代
     * @param head
     * @return
     */
    public static ListNode reverseList3(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode result = null;
        ListNode h = head;
        while (h != null){
            ListNode tmp = h.next;
            h.next = result;
            result = h;
            h = tmp;
        }
        return result;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}




